import java.util.*;

/**
 * @author : xwj
 * @date : 2021/9/22 22:36
 * @description : 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
 * @class : test3
 **/

public class test3 {

    //1. 254 ms	55 MB
    //使用递归的方法，将每一个字符开始的字符串都遍历一遍，找到最大的子串
    public static int lengthOfLongestSubstring(String s) {
        if(s.length() < 2) {
            return s.length();
        }
        int max_len = 0;
        max_len = findMaxLen(s, s.length(), 0, max_len);
        return max_len;
    }

    private static int findMaxLen(String s,int len,int index, int max_len) {
        if (len - index < max_len) {
            return max_len;
        }
        String str = "";
        for (int i = index; i < len; i++) {
            if (!str.contains(String.valueOf(s.charAt(i)))) {
                str = str + s.charAt(i);
            } else {
                break;
            }
        }
        max_len = findMaxLen(s, len, ++index, max_len);
        return Math.max(max_len, str.length());
    }

    //2. 18 ms	38.5 MB
    public static int lengthOfLongestSubstring2(String s) {
        if(s.length() < 2) {
            return s.length();
        }
        int max_len = 0;
        Deque<Character> str = new ArrayDeque<>();
        for (int i = 0; i < s.length(); i++) {
            if (!str.contains(s.charAt(i))) {
                str.add(s.charAt(i));
            } else {
                max_len = Math.max(max_len, str.size());
                while (str.contains(s.charAt(i))) {
                    str.pop();
                }
                str.add(s.charAt(i));
            }
        }
        return Math.max(max_len, str.size());
    }

    public static void main(String[] args) {
        String s = "pwwkew";
        System.out.println(lengthOfLongestSubstring2(s));
    }

}
